Distributed-service environments may include multiple different nodes that each replicate work that each other node performs. For instance, a distributed storage service may include multiple different storage servers, each of which stores a user's data in response to receiving storage requests from the user. In some instances, these different storage servers reside geographically remote from one another, thus protecting the user's data in the event of an outage or catastrophic event at one of the geographic locations.
In another example, a distributed computational service may include multiple different computational servers. Each of these computational servers may compute requested computational problems for the purpose of verifying the computed results with each other computational service. Many other distributed-service environments exist, with these environments including multiple different entities that each perform and replicate operations requested by a user or other entity.
In some instances, the entities that perform the requested operations may desire to generally remain caught up with one another. For instance, when a user requests to store a large batch of data on a distributed storage service, the distributed storage service may attempt to ensure that none of the replicated storage nodes has a backlog of storage requests to process that is grossly larger than a backlog of the other replicated storage nodes. While the distributed storage service may simply stop receipt of user requests to allow the backlogged storage node to catch up, such a solution may prove grating to the user of the distributed service.